/*
题目链接 :https://leetcode.cn/problems/palindrome-partitioning-iii/description/
*/

//题解代码 :  
class Solution {
public:
    #define INF 0x3f3f3f3f
    int palindromePartition(string s, int k) {
        int n = s.size();
        
        //预处理 s[i....j]的子串变成回文串需要修改几个字符
        vector<vector<int>> cost(n,vector<int>(n));
        auto compute_cost = [&](int i,int j)->int{
            int ret = 0;
            for(int f=i,e=j;f<e;++f,--e){
                ret += (s[f]!=s[e]);
            }
            return ret;
        };
        for(int i=0;i<n;++i){
            for(int j=i;j<n;++j){
                cost[i][j] = compute_cost(i,j);
            }
        }

        //dp[i][j]:把s[i.....n-1]划分成j个回文串的最小花费
        //枚举 i <= m < n 为分割点, dp[i][j] = min(dp[m+1][j-1]+cost[i][m])
        vector<vector<int>> dp(n+1,vector<int>(k+1,INF));
        for(int i=0;i<n;++i) dp[i][1] = cost[i][n-1];
        for(int j=2;j<=k;++j){
            for(int i=n-1;i>=0;--i){
                for(int m=i;m<n;++m){
                    dp[i][j] = min(dp[i][j],dp[m+1][j-1]+cost[i][m]);
                }
            }
        }
        return dp[0][k];
    }
};
